《离散数学》第一学期期末试卷B (精选06)

一、填空（本大题共 5 个空，每空 2 分，总计 10 分）

1. 设 $A$ 和 $B$ 为有限集，$|A| = m$，$|B| = n$，则有 ______ 个从 $A$ 到 $B$ 的关系，有 ______ 个从 $A$ 到 $B$ 的函数，其中当 $m \leq n$ 时有 ______ 个单射（入射），当 $m = n$ 时，有 ______ 个双射。

查看答案与解析

答案：$2^{mn}$；$n^m$；$P(n,m)$ (或 $n(n-1)\dots(n-m+1)$)；$n!$

解析：

1. 从 $A$ 到 $B$ 的关系：

   • 关系是 $A \times B$ 的子集。
   • $|A \times B| = |A| \cdot |B| = m \cdot n$。
   • 集合 $A \times B$ 的子集个数为 $2^{|A \times B|} = 2^{mn}$。

2. 从 $A$ 到 $B$ 的函数：

   • 对于 $A$ 中的每一个元素，在 $B$ 中都有 $n$ 种选择。
   • 根据乘法原理，共有 $n \times n \times \dots \times n$（共 $m$ 个 $n$）$= n^m$ 种。

3. 从 $A$ 到 $B$ 的单射（$m \leq n$）：

   • 第一个元素有 $n$ 种选择，第二个有 $n-1$ 种，...，第 $m$ 个有 $n-m+1$ 种。
   • 即排列数 $P(n, m) = \frac{n!}{(n-m)!}$。

4. 从 $A$ 到 $B$ 的双射（$m = n$）：

   • 当 $m=n$ 时，单射即为双射。
   • 共有 $P(n, n) = n!$ 种。

方法总结：

• 关系：考虑 $A \times B$ 的幂集，总数为 $2^{|A| \cdot |B|}$。
• 函数：每个自变量都有因变量集合大小的选择数，总数为 $|B|^{|A|}$。
• 单射：从 $|B|$ 中选出 $|A|$ 个进行排列，$P(|B|, |A|)$。

---

难度: ⭐
考点: #集合论 #计数原理 #函数与关系

💡 学习锦囊

📖 相关公式与知识点:

• 关系总数：$2^{|A| \cdot |B|}$
• 函数总数：$|B|^{|A|}$
• 单射总数 ($|A| \le |B|$)：$P(|B|, |A|)$
• 双射总数 ($|A| = |B|$)：$|A|!$

思路分析

这类题目属于基础计数问题。关键是分清“底数”和“指数”的关系。对于函数 $f: A \to B$，是 $A$ 中的元素在做选择，所以是 $|B|^{|A|}$。

易错点

• 混淆函数总数和关系总数。
• 记反函数总数的底数和幂（常见错误写成 $m^n$）。

🔄 举一反三

1. 设 $A=\{1,2,3\}, B=\{a,b\}$，求从 $A$ 到 $B$ 的关系数。
   查看练习答案与解析

   答案：$2^6 = 64$
   解析：$|A|=3, |B|=2$，故关系数为 $2^{3 \times 2} = 2^6 = 64$。

2. 设 $A=\{1,2\}, B=\{a,b,c\}$，求从 $A$ 到 $B$ 的单射数。
   查看练习答案与解析

   答案：$6$
   解析：$|A|=2, |B|=3$，单射数为 $P(3, 2) = 3 \times 2 = 6$。

2. 集合 $A = \{n^2 \mid n \in \mathbb{N}\}$ 是（是/不是）可数集。

查看答案与解析

答案：是

解析：

1. 定义回顾：如果一个集合 $A$ 与自然数集 $\mathbb{N}$ 之间存在一个双射（一一对应），则称 $A$ 为可数无穷集。凡是有限集或可数无穷集统称为可数集。
2. 构造映射：定义映射 $f: \mathbb{N} \to A$，使得对于任意 $n \in \mathbb{N}$，$f(n) = n^2$。
3. 验证双射：
   • 单射性：若 $n_1^2 = n_2^2$，且 $n_1, n_2 \in \mathbb{N}$（$\mathbb{N}=\{0, 1, 2, \dots\}$ 或 $\{1, 2, \dots\}$，此处 $n \ge 0$），则 $n_1 = n_2$。
   • 满射性：根据集合 $A$ 的定义，对于 $A$ 中任意元素 $y$，必存在 $n \in \mathbb{N}$ 使得 $y = n^2$。
4. 结论：因为存在从 $\mathbb{N}$ 到 $A$ 的双射，所以 $A$ 是可数集。

方法总结： 判断可数性的常用技巧：

• 能够按某种规则排成一列（不遗漏、不重复）的集合都是可数的。
• 可数集的任何子集都是可数的。
• 两个可数集的笛卡尔积仍是可数的。

---

难度: ⭐
考点: #集合论 #可数集 #基数

💡 学习锦囊

📖 相关公式与知识点:

• 可数集的定义：基数为 $\aleph_0$ 的集合。
• 任何无穷集的无穷子集如果是无穷的，且原集可数，则子集也可数。

思路分析

判断一个无穷集是否可数，最直接的方法是看能否将其元素排成一个序列 $a_1, a_2, a_3, \dots$。对于 $A=\{0, 1, 4, 9, \dots\}$，显然可以排序。

🔄 举一反三

1. 集合 $A = \{2n \mid n \in \mathbb{N}\}$ 是可数集吗？
   查看练习答案与解析

   答案：是
   解析：偶数集与自然数集存在双射 $f(n) = 2n$，故为可数集。

2. 整数集 $\mathbb{Z}$ 是可数集吗？
   查看练习答案与解析

   答案：是
   解析：可以将整数集排成如下序列：$0, 1, -1, 2, -2, 3, -3, \dots$。通过这种排序方式，每个整数都会在有限步内出现，因此 $\mathbb{Z}$ 是可数集。

二、计算（本大题共 2 小题，每小题 10 分，总计 20 分）

1. 用推导法求下列公式的主合取范式和主析取范式： $((\neg P \lor Q) \rightarrow R)$

查看答案与解析

答案：

• 主析取范式 (PDNF)：$(\neg P \land \neg Q \land R) \lor (\neg P \land Q \land R) \lor (P \land \neg Q \land \neg R) \lor (P \land \neg Q \land R) \lor (P \land Q \land R)$
  或表示为：$\sum(1, 3, 4, 5, 7)$ 或 $m_1 \lor m_3 \lor m_4 \lor m_5 \lor m_7$
• 主合取范式 (PCNF)：$(P \lor Q \lor R) \land (P \lor \neg Q \lor R) \land (\neg P \lor \neg Q \lor R)$
  或表示为：$\prod(0, 2, 6)$ 或 $M_0 \land M_2 \land M_6$

解析：

第一步：公式化简 利用蕴涵等价式 $A \rightarrow B \equiv \neg A \lor B$： $((\neg P \lor Q) \rightarrow R) \equiv \neg(\neg P \lor Q) \lor R$$\equiv (P \land \neg Q) \lor R$ （摩根定律）

第二步：求主析取范式 (PDNF) 通过引入缺失的变元： $(P \land \neg Q \land (R \lor \neg R)) \lor (R \land (P \lor \neg P) \land (Q \lor \neg Q))$$\equiv (P \land \neg Q \land R) \lor (P \land \neg Q \land \neg R) \lor (R \land P \land Q) \lor (R \land P \land \neg Q) \lor (R \land \neg P \land Q) \lor (R \land \neg P \land \neg Q)$ 合并重复项： $\equiv (P \land \neg Q \land R) \lor (P \land \neg Q \land \neg R) \lor (P \land Q \land R) \lor (\neg P \land Q \land R) \lor (\neg P \land \neg Q \land R)$ 对应小项下标：$101, 100, 111, 011, 001 \Rightarrow m_5, m_4, m_7, m_3, m_1$。 故 PDNF 为 $m_1 \lor m_3 \lor m_4 \lor m_5 \lor m_7$。

第三步：求主合取范式 (PCNF) 方法一：利用 PDNF 中缺失的小项下标对应的最大项。 缺失下标为：$0, 2, 6$。 对应最大项：$M_0, M_2, M_6$。 故 PCNF 为 $(P \lor Q \lor R) \land (P \lor \neg Q \lor R) \land (\neg P \lor \neg Q \lor R)$。

方法总结：

1. 求 PDNF：
   • 化简公式为 $\neg, \land, \lor$ 形式。
   • 利用分配律展开。
   • 对不含变元 $X$ 的项合取 $(X \lor \neg X)$。
2. 求 PCNF：
   • 找出 PDNF 缺失的下标。
   • 将下标 $i$ 转换为二进制，0 对应变量本身，1 对应变量否定，用析取 ($\lor$) 连接得到最大项 $M_i$。

---

难度: ⭐⭐
考点: #数理逻辑 #主范式 #蕴涵等价式

💡 学习锦囊

📖 相关公式与知识点:

• 蕴涵等价式：$P \to Q \equiv \neg P \lor Q$
• 德·摩根定律：$\neg(P \lor Q) \equiv \neg P \land \neg Q$
• 小项 ($m_i$)：变元及其否定的合取。
• 最大项 ($M_i$)：变元及其否定的析取。

思路分析

1. 先利用等价变换将公式化简为只含 $\neg, \land, \lor$ 的形式。
2. 求 PDNF 时，对不含某个变元的项合取 $(X \lor \neg X)$。
3. 求 PCNF 时，最快的方法是先求出 PDNF，然后找缺失的下标。

易错点

• 在化简 $\neg(\neg P \lor Q)$ 时忘记变号，写成 $P \land Q$。
• 在对应小项下标时，注意变量顺序（通常为 $P, Q, R$）。

🔄 举一反三

1. 求 $P \rightarrow Q$ 的主析取范式。
   查看练习答案与解析

   答案：$(\neg P \land \neg Q) \lor (\neg P \land Q) \lor (P \land Q)$
   解析：$P \to Q \equiv \neg P \lor Q \equiv (\neg P \land (Q \lor \neg Q)) \lor (Q \land (P \lor \neg P)) \equiv (\neg P \land Q) \lor (\neg P \land \neg Q) \lor (P \land Q)$。

2. 求 $P \land (P \to Q)$ 的主析取范式。
   查看练习答案与解析

   答案：$P \land Q$
   解析：$P \land (P \to Q) \equiv P \land (\neg P \lor Q) \equiv (P \land \neg P) \lor (P \land Q) \equiv F \lor (P \land Q) \equiv P \land Q$。

2. 设 $A = \{1, 2, 3, 4\}$，$A$ 上二元关系 $R = \{\langle 1,2 \rangle, \langle 2,2 \rangle, \langle 2,4 \rangle, \langle 3,4 \rangle\}$，求其自反闭包、对称闭包、传递闭包。

查看答案与解析

答案：

• 自反闭包 $r(R)$：$R \cup \{\langle 1,1 \rangle, \langle 2,2 \rangle, \langle 3,3 \rangle, \langle 4,4 \rangle\}$
• 对称闭包 $s(R)$：$R \cup \{\langle 2,1 \rangle, \langle 4,2 \rangle, \langle 4,3 \rangle\}$
• 传递闭包 $t(R)$：$R \cup \{\langle 1,4 \rangle\}$

解析：

1. 自反闭包 $r(R)$：

   • 需补充所有 $\langle x, x \rangle$ 形式的序对。
   • $r(R) = R \cup \{\langle 1,1 \rangle, \langle 2,2 \rangle, \langle 3,3 \rangle, \langle 4,4 \rangle\}$。
   • 结果为：$\{\langle 1,2 \rangle, \langle 2,2 \rangle, \langle 2,4 \rangle, \langle 3,4 \rangle, \langle 1,1 \rangle, \langle 3,3 \rangle, \langle 4,4 \rangle\}$。

2. 对称闭包 $s(R)$：

   • 需补充所有反向序对，即 $R \cup R^{-1}$。
   • $R^{-1} = \{\langle 2,1 \rangle, \langle 2,2 \rangle, \langle 4,2 \rangle, \langle 4,3 \rangle\}$。
   • $s(R) = \{\langle 1,2 \rangle, \langle 2,2 \rangle, \langle 2,4 \rangle, \langle 3,4 \rangle, \langle 2,1 \rangle, \langle 4,2 \rangle, \langle 4,3 \rangle\}$。

3. 传递闭包 $t(R)$：

   • 检查是否存在 $\langle x,y \rangle, \langle y,z \rangle \in R$ 但 $\langle x,z \rangle \notin R$。
   • 由 $\langle 1,2 \rangle, \langle 2,4 \rangle \in R$ 可推得 $\langle 1,4 \rangle$ 应当加入。
   • 检查新集合 $\{\langle 1,2 \rangle, \langle 2,2 \rangle, \langle 2,4 \rangle, \langle 3,4 \rangle, \langle 1,4 \rangle\}$，已满足传递性。
   • 故 $t(R) = \{\langle 1,2 \rangle, \langle 2,2 \rangle, \langle 2,4 \rangle, \langle 3,4 \rangle, \langle 1,4 \rangle\}$。

方法总结：

• 自反闭包 $r(R)$：$R \cup I_A$，即给关系矩阵对角线全填 1。
• 对称闭包 $s(R)$：$R \cup R^{-1}$，即关于对角线对称地补全 1。
• 传递闭包 $t(R)$：
  1. Warshall 算法（适用于矩阵）。
  2. 路径法：找出所有长度 $\ge 1$ 的路径的起点和终点。在本题中，路径 $1 \to 2 \to 4$ 意味着必须包含 $\langle 1, 4 \rangle$。

---

难度: ⭐⭐
考点: #集合论 #二元关系 #闭包运算

💡 学习锦囊

📖 相关公式与知识点:

• $r(R) = R \cup I_A$
• $s(R) = R \cup R^{-1}$
• $t(R) = R \cup R^2 \cup R^3 \cup \dots$

思路分析

• 自反闭包：对角线补全。
• 对称闭包：关于对角线镜像补全。
• 传递闭包：寻找“路径”，如果存在从 $a$ 到 $b$ 的路径，则必须有直接的关系 $\langle a, b \rangle$。

🔄 举一反三

1. 若 $R = \{\langle 1,1 \rangle\}$ 在 $\{1,2\}$ 上，求 $r(R)$。
   查看练习答案与解析

   答案：$\{\langle 1,1 \rangle, \langle 2,2 \rangle\}$
   解析：需加上全等关系 $I_A = \{\langle 1,1 \rangle, \langle 2,2 \rangle\}$。

2. 若 $R = \{\langle 1,2 \rangle, \langle 2,3 \rangle\}$，求 $t(R)$。
   查看练习答案与解析

   答案：$\{\langle 1,2 \rangle, \langle 2,3 \rangle, \langle 1,3 \rangle\}$
   解析：存在路径 $1 \to 2$ 和 $2 \to 3$，根据传递性，必须包含 $\langle 1,3 \rangle$。

三、证明（本大题共 2 小题，第 1 小题 5 分，第 2 小题 10 分，总计 15 分）

1. 设 $A, B, C$ 是三个集合，证明： $(A \cap B) - C = (A - C) \cap B$

查看答案与解析

答案：见解析

解析：

利用集合代数定律进行推导：

• 第一步：利用差集的定义，$X - Y = X \cap \overline{Y}$。 左式 $(A \cap B) - C = (A \cap B) \cap \overline{C}$
• 第二步：利用交集的结合律。 $(A \cap B) \cap \overline{C} = A \cap (B \cap \overline{C})$
• 第三步：利用交集的交换律。 $A \cap (B \cap \overline{C}) = A \cap (\overline{C} \cap B)$
• 第四步：再次利用交集的结合律。 $A \cap (\overline{C} \cap B) = (A \cap \overline{C}) \cap B$
• 第五步：利用差集的定义。 $(A \cap \overline{C}) \cap B = (A - C) \cap B$
• 结论：左式 = 右式，证毕。

方法总结： 证明集合恒等式的代数法步骤：

1. 消去差集符号（使用 $X - Y = X \cap \overline{Y}$）。
2. 利用分配律、结合律或交换律调整结构。
3. 利用德·摩根定律处理补集。
4. 利用吸收律或幂等律简化。

---

难度: ⭐
考点: #集合论 #集合恒等式证明 #差集定义

💡 学习锦囊

📖 相关公式与知识点:

• $A - B = A \cap \overline{B}$
• 结合律：$(A \cap B) \cap C = A \cap (B \cap C)$
• 交换律：$A \cap B = B \cap A$

思路分析

证明集合恒等式有两种常用方法：

1. 成员隶属法：证明 $x \in LHS \iff x \in RHS$。
2. 集合代数法：利用已知的定律进行等价变换（本题采用此法，更为简洁）。

🔄 举一反三

1. 证明 $A - (B \cup C) = (A - B) \cap (A - C)$。
   查看练习答案与解析

   答案：见解析
   解析： $A - (B \cup C) = A \cap \overline{B \cup C}$$= A \cap (\overline{B} \cap \overline{C})$ （德·摩根定律） $= (A \cap A) \cap (\overline{B} \cap \overline{C})$ （幂等律） $= (A \cap \overline{B}) \cap (A \cap \overline{C})$ （交换律、结合律） $= (A - B) \cap (A - C)$。

2. 证明 $A \cap (B - C) = (A \cap B) - (A \cap C)$。
   查看练习答案与解析

   答案：见解析
   解析： 左式 $= A \cap B \cap \overline{C}$。 右式 $= (A \cap B) \cap \overline{A \cap C} = (A \cap B) \cap (\overline{A} \cup \overline{C})$$= (A \cap B \cap \overline{A}) \cup (A \cap B \cap \overline{C})$$= \emptyset \cup (A \cap B \cap \overline{C}) = A \cap B \cap \overline{C}$。 左式 $=$ 右式。

2. 证明等价式： $(\exists x)(A(x) \to B(x)) \Leftrightarrow (\forall x)A(x) \to (\exists x)B(x)$

查看答案与解析

答案：见解析

解析：

利用谓词逻辑等价式进行推导：

• 第一步：利用蕴涵等价式 $P \to Q \equiv \neg P \lor Q$ 处理左式。 $(\exists x)(A(x) \to B(x)) \iff (\exists x)(\neg A(x) \lor B(x))$
• 第二步：利用存在量词对析取式的分配律。 $(\exists x)(\neg A(x) \lor B(x)) \iff (\exists x)\neg A(x) \lor (\exists x)B(x)$
• 第三步：利用量词否定等价式 $\neg (\forall x)P(x) \iff (\exists x)\neg P(x)$。 $(\exists x)\neg A(x) \lor (\exists x)B(x) \iff \neg (\forall x)A(x) \lor (\exists x)B(x)$
• 第四步：再次利用蕴涵等价式。 $\neg (\forall x)A(x) \lor (\exists x)B(x) \iff (\forall x)A(x) \to (\exists x)B(x)$
• 结论：等价式成立。

方法总结： 证明谓词逻辑等价式的核心步骤：

1. 消去所有 $\to$ 和 $\leftrightarrow$ 符号。
2. 将 $\neg$ 移至紧靠原子谓词公式处（利用德·摩根定律和量词否定律）。
3. 利用量词的分配律或移入律调整量词范围。
4. 在必要时进行变量更名以避免冲突。

---

难度: ⭐⭐
考点: #数理逻辑 #谓词逻辑 #量词分配律 #蕴涵等价式

💡 学习锦囊

📖 相关公式与知识点:

• $(\exists x)(P(x) \lor Q) \iff (\exists x)P(x) \lor Q$ （$Q$ 中不含 $x$）
• $(\exists x)(P(x) \lor Q(x)) \iff (\exists x)P(x) \lor (\exists x)Q(x)$
• 量词转换律：$\neg (\forall x)A(x) \iff (\exists x)\neg A(x)$

思路分析

谓词逻辑证明通常涉及将蕴涵式转换为析取式，然后利用量词的分配律（$\exists$ 对 $\lor$ 分配，$\forall$ 对 $\land$ 分配）和移入/移出律来处理。

🔄 举一反三

1. 证明 $(\forall x)(A(x) \to B) \iff (\exists x)A(x) \to B$（其中 $B$ 不含 $x$）。
   查看练习答案与解析

   答案：见解析
   解析： $(\forall x)(A(x) \to B) \iff (\forall x)(\neg A(x) \lor B)$$\iff (\forall x)\neg A(x) \lor B$ （因为 $B$ 中不含 $x$） $\iff \neg (\exists x)A(x) \lor B$$\iff (\exists x)A(x) \to B$。

2. 证明 $\neg (\exists x)(P(x) \land Q(x)) \iff (\forall x)(P(x) \to \neg Q(x))$。
   查看练习答案与解析

   答案：见解析
   解析： 左边 $\iff (\forall x)\neg (P(x) \land Q(x))$$\iff (\forall x)(\neg P(x) \lor \neg Q(x))$$\iff (\forall x)(P(x) \to \neg Q(x))$。 右边证毕。

四、（本大题共 15 分）将下列命题推理符号化并给出形式证明：

已知张三或李四的彩票中奖了；如果张三的彩票中奖了，那么你是知道的；如果李四的彩票中奖了，那么王五的彩票也中奖了；现在你不知道张三的彩票中奖。所以李四和王五的彩票都中奖了。

查看答案与解析

答案：见解析

解析：

第一步：符号化 设命题如下：

• $P$：张三的彩票中奖了
• $Q$：李四的彩票中奖了
• $R$：你知道张三的彩票中奖
• $S$：王五的彩票中奖了

前提：

1. $P \lor Q$
2. $P \to R$
3. $Q \to S$
4. $\neg R$

结论：$Q \land S$

第二步：形式证明 ① $P \to R$ （前提 2） ② $\neg R$ （前提 4） ③ $\neg P$ （①②，拒取式 MT） ④ $P \lor Q$ （前提 1） ⑤ $Q$ （③④，析取三段论 DS） ⑥ $Q \to S$ （前提 3） ⑦ $S$ （⑤⑥，肯定前件式 MP） ⑧ $Q \land S$ （⑤⑦，合取引入）

结论得证。

方法总结：

1. 符号化：给每个原子命题分配一个大写字母。
2. 提取前提：将自然语言翻译成逻辑表达式。
3. 选择推导规则：
   • 看到否定式，考虑拒取式 (MT) 或析取三段论 (DS)。
   • 看到蕴涵式，考虑肯定前件 (MP)。
   • 最后使用合取或析取规则组合成结论。

---

难度: ⭐⭐
考点: #数理逻辑 #自然推理系统 #命题逻辑符号化

💡 学习锦囊

📖 相关公式与知识点:

• 析取三段论 (DS)：$(P \lor Q) \land \neg P \Rightarrow Q$
• 拒取式 (MT)：$(P \to Q) \land \neg Q \Rightarrow \neg P$
• 肯定前件 (MP)：$(P \to Q) \land P \Rightarrow Q$
• 合取引入：$P, Q \Rightarrow P \land Q$

思路分析

符号化时，注意捕捉“如果...那么...”这种蕴涵结构。证明时，观察前提中的否定项（$\neg R$），寻找与之对应的项进行拒取，逐步推出目标。

🔄 举一反三

1. 若 $P \to Q, Q \to R, P$ 为前提，证明 $R$。
   查看练习答案与解析

   答案：见解析
   解析： ① $P \to Q$ （前提） ② $P$ （前提） ③ $Q$ （①②，MP） ④ $Q \to R$ （前提） ⑤ $R$ （③④，MP）

2. 证明：若前提为 $P \lor Q, \neg P$，结论为 $Q$。
   查看练习答案与解析

   答案：见解析
   解析： ① $P \lor Q$ （前提） ② $\neg P$ （前提） ③ $Q$ （①②，DS 规则） 直接得证。

五、（本大题共 10 分）

设复数集合 $C = \{a + bi \mid a, b \in \mathbb{R}, a \neq 0\}$，定义 $C$ 上二元关系 $R$：$\langle a + bi, c + di \rangle \in R$ 当且仅当 $ac > 0$，证明：$R$ 为等价关系。

查看答案与解析

答案：见解析

解析：

要证明 $R$ 是等价关系，需证明其满足自反性、对称性和传递性。

1. 自反性： 对于任意 $z = a + bi \in C$，由于 $a \neq 0$，则 $a \cdot a = a^2 > 0$。 根据关系 $R$ 的定义，有 $\langle z, z \rangle \in R$。故 $R$ 满足自反性。

2. 对称性： 若 $\langle a + bi, c + di \rangle \in R$，则 $ac > 0$。 由于实数乘法满足交换律，故 $ca = ac > 0$。 由此得 $\langle c + di, a + bi \rangle \in R$。故 $R$ 满足对称性。

3. 传递性： 若 $\langle a + bi, c + di \rangle \in R$ 且 $\langle c + di, e + fi \rangle \in R$， 则有 $ac > 0$ 且 $ce > 0$。 两者相乘得：$(ac)(ce) > 0 \Rightarrow a e c^2 > 0$。 由于 $c \neq 0$，故 $c^2 > 0$，从而推出 $ae > 0$。 根据定义，有 $\langle a + bi, e + fi \rangle \in R$。故 $R$ 满足传递性。

结论：综上所述，$R$ 是 $C$ 上的等价关系。

方法总结： 证明等价关系的标准步骤：

1. 自反性：证明对于任意 $x$，$\langle x, x \rangle$ 满足关系定义。
2. 对称性：假设 $\langle x, y \rangle$ 满足定义，证明 $\langle y, x \rangle$ 也满足。
3. 传递性：假设 $\langle x, y \rangle$ 和 $\langle y, z \rangle$ 满足定义，证明 $\langle x, z \rangle$ 也满足。

---

难度: ⭐⭐
考点: #集合论 #二元关系 #等价关系证明

💡 学习锦囊

📖 相关公式与知识点:

• 等价关系定义：同时满足自反、对称、传递的二元关系。
• 实数性质：若 $ac > 0$ 且 $ce > 0$，则 $ae > 0$。

思路分析

证明等价关系是离散数学的经典题型。只需机械地核对三个定义即可。在本题中，关系仅取决于复数的实部 $a$，虚部 $b$ 不影响结果。

🔄 举一反三

1. 在 $\mathbb{Z}$ 上定义 $R$：$\langle x, y \rangle \in R \iff x \equiv y \pmod m$。证明 $R$ 是等价关系。
   查看练习答案与解析

   答案：见解析
   解析：

   • 自反：$x-x=0$ 能被 $m$ 整除。
   • 对称：若 $x-y=km$，则 $y-x=(-k)m$。
   • 传递：若 $x-y=k_1 m, y-z=k_2 m$，则 $x-z=(k_1+k_2)m$。
2. 在 $\mathbb{R}$ 上定义 $R$：$\langle x, y \rangle \in R \iff |x| = |y|$。证明 $R$ 是等价关系。
   查看练习答案与解析

   答案：见解析
   解析：

   • 自反：$|x|=|x|$ 显然成立。
   • 对称：若 $|x|=|y|$，则 $|y|=|x|$ 显然成立。
   • 传递：若 $|x|=|y|$ 且 $|y|=|z|$，则 $|x|=|z|$。

六、（本大题 10 分）

证明：若 $A \approx C$ 且 $B \approx D$，则 $A \times B \approx C \times D$。（注：$\approx$ 表示集合等势，即基数相等）

查看答案与解析

答案：见解析

解析：

要证明两个集合等势，只需证明它们之间存在一个双射。

• 已知条件：

  1. $A \approx C \implies$ 存在双射 $f: A \to C$。
  2. $B \approx D \implies$ 存在双射 $g: B \to D$。

• 构造映射： 定义映射 $h: A \times B \to C \times D$，使得对于任意 $\langle a, b \rangle \in A \times B$：

  $$h(\langle a, b \rangle) = \langle f(a), g(b) \rangle$$

• 验证双射性：

  1. 单射性： 若 $h(\langle a_1, b_1 \rangle) = h(\langle a_2, b_2 \rangle)$，则 $\langle f(a_1), g(b_1) \rangle = \langle f(a_2), g(b_2) \rangle$。 根据序对相等的定义，得 $f(a_1) = f(a_2)$ 且 $g(b_1) = g(b_2)$。 因为 $f$ 和 $g$ 均为单射，所以 $a_1 = a_2$ 且 $b_1 = b_2$。 由此推得 $\langle a_1, b_1 \rangle = \langle a_2, b_2 \rangle$。故 $h$ 是单射。

  2. 满射性： 对于任意 $\langle c, d \rangle \in C \times D$，由于 $f$ 是从 $A$ 到 $C$ 的满射，故存在 $a \in A$ 使得 $f(a) = c$。 同理，存在 $b \in B$ 使得 $g(b) = d$。 于是存在 $\langle a, b \rangle \in A \times B$，使得 $h(\langle a, b \rangle) = \langle f(a), g(b) \rangle = \langle c, d \rangle$。故 $h$ 是满射。

结论：由于存在从 $A \times B$ 到 $C \times D$ 的双射 $h$，故 $A \times B \approx C \times D$。

方法总结： 证明集合等势的常用构造方法：

1. 直接构造双射：如本题中的分量映射。
2. 分段构造：处理如 $\mathbb{N}$ 到 $\mathbb{Z}$ 的映射。
3. Schröder-Bernstein 定理：只需证明存在从 $A$ 到 $B$ 的单射且存在从 $B$ 到 $A$ 的单射。

---

难度: ⭐⭐
考点: #集合论 #集合等势 #双射 #笛卡尔积

💡 学习锦囊

📖 相关公式与知识点:

• 集合等势定义：存在双射 $f: A \to B \iff A \approx B$。
• 双射证明：证明既是单射又是满射。

思路分析

证明笛卡尔积的等势，最自然的思路就是分量对应。利用已知的两个分量的双射，组合成一个新的映射。

🔄 举一反三

1. 证明若 $A \approx B$，则 $\mathcal{P}(A) \approx \mathcal{P}(B)$（其中 $\mathcal{P}$ 表示幂集）。
   查看练习答案与解析

   答案：见解析
   解析： 已知存在双射 $f: A \to B$。 定义 $F: \mathcal{P}(A) \to \mathcal{P}(B)$ 为 $F(S) = \{f(x) \mid x \in S\}$。 易证 $F$ 为双射。

2. 证明闭区间 $[0, 1]$ 与 $[0, 2]$ 等势。
   查看练习答案与解析

   答案：见解析
   解析： 定义函数 $f: [0, 1] \to [0, 2]$ 为 $f(x) = 2x$。 该函数显然是双射，故 $[0, 1] \approx [0, 2]$。

七、（本大题 10 分）

设集合 $G = \{2^m 3^n \mid m, n \in \mathbb{I}\}$，$\times$ 是普通乘法（此处 $\mathbb{I}$ 表示整数集 $\mathbb{Z}$），证明：$\langle G, \times \rangle$ 是一个群。

查看答案与解析

答案：见解析

解析：

证明一个代数系统是群，需要验证其满足四个基本性质：封闭性、结合律、单位元（幺元）和逆元。

1. 封闭性： 对于任意 $x, y \in G$，设 $x = 2^{m_1} 3^{n_1}$，$y = 2^{m_2} 3^{n_2}$，其中 $m_1, n_1, m_2, n_2 \in \mathbb{Z}$。 则 $x \times y = (2^{m_1} 3^{n_1}) \times (2^{m_2} 3^{n_2}) = 2^{m_1+m_2} 3^{n_1+n_2}$。 由于 $m_1+m_2 \in \mathbb{Z}$ 且 $n_1+n_2 \in \mathbb{Z}$，根据 $G$ 的定义，有 $x \times y \in G$。故 $G$ 对乘法封闭。

2. 结合律： 由于 $G$ 中的元素都是实数，且普通乘法在实数集上满足结合律，故 $\langle G, \times \rangle$ 满足结合律。

3. 单位元： 取 $m=0, n=0$，得 $2^0 3^0 = 1$。 显然 $1 \in G$。且对于任意 $x \in G$，$x \times 1 = 1 \times x = x$。 故 $1$ 是 $G$ 中的单位元。

4. 逆元： 对于任意 $x = 2^m 3^n \in G$，由于 $m, n \in \mathbb{Z}$，则 $-m, -n \in \mathbb{Z}$。 取 $y = 2^{-m} 3^{-n}$，则 $y \in G$。 且 $x \times y = 2^{m-m} 3^{n-n} = 2^0 3^0 = 1$。 故每一个元素在 $G$ 中都有逆元。

结论：综上所述，$\langle G, \times \rangle$ 是一个群。

方法总结： 证明群的方法（群的四公理）：

1. 封闭性：任取两元素运算后仍属于该集合。
2. 结合律：通常利用数集或矩阵运算的已知性质。
3. 单位元：寻找元素 $e$ 使得 $a * e = e * a = a$。
4. 逆元：对于任意 $a$，寻找 $a^{-1}$ 使得 $a * a^{-1} = e$。

---

难度: ⭐⭐
考点: #代数结构 #群论 #群的定义证明

💡 学习锦囊

📖 相关公式与知识点:

• 群的四个公理：封闭性、结合律、单位元、逆元。
• 整数性质：整数加法封闭。

思路分析

本题属于典型的群定义验证题。重点在于利用指数运算性质（$a^m a^n = a^{m+n}$）将乘法运算转化为整数加法运算，从而利用整数集的性质完成证明。

🔄 举一反三

1. 证明 $\langle \mathbb{Z}, + \rangle$ 是一个群。
   查看练习答案与解析

   答案：见解析
   解析：

   • 封闭：整数加整数仍为整数。
   • 结合：$(a+b)+c = a+(b+c)$。
   • 单位元：$0$。
   • 逆元：$x$ 的逆元为 $-x$。
2. 设 $G = \{1, -1, i, -i\}$，证明 $G$ 对复数乘法构成一个群。
   查看练习答案与解析

   答案：见解析
   解析：

   • 封闭：观察乘法表或指出这些数都是 $x^4=1$ 的根。
   • 单位元：$1$。
   • 逆元：$1^{-1}=1, (-1)^{-1}=-1, i^{-1}=-i, (-i)^{-1}=i$。

八、（本大题 10 分）

设实数集合 $\mathbb{R}$，$+$ 和 $\times$ 是普通加法和乘法，定义映射 $f: \mathbb{R} \to \mathbb{R}$，对于任意 $x \in \mathbb{R}$，$f(x) = e^x$，证明 $f$ 是从 $\langle \mathbb{R}, + \rangle$ 到 $\langle \mathbb{R}, \times \rangle$ 的单一同态（单同态）。

查看答案与解析

答案：见解析

解析：

要证明 $f$ 是从 $\langle \mathbb{R}, + \rangle$ 到 $\langle \mathbb{R}, \times \rangle$ 的单同态，需要证明两个方面：$f$ 是同态映射，且 $f$ 是单射。

1. 同态证明： 对于任意 $x, y \in \mathbb{R}$： 左式 $f(x + y) = e^{x + y}$ 右式 $f(x) \times f(y) = e^x \times e^y$ 根据指数函数的性质 $e^{x+y} = e^x \cdot e^y$，可得：

   $$f(x + y) = f(x) \times f(y)$$

   因此，$f$ 是从 $\langle \mathbb{R}, + \rangle$ 到 $\langle \mathbb{R}, \times \rangle$ 的同态映射。

2. 单射证明： 对于任意 $x_1, x_2 \in \mathbb{R}$，若 $f(x_1) = f(x_2)$，则：

   $$e^{x_1} = e^{x_2}$$

   两边取自然对数 $\ln$（由于指数函数 $e^x$ 在实数范围内是严格单调递增的）：

   $$\ln(e^{x_1}) = \ln(e^{x_2}) \implies x_1 = x_2$$

   根据单射定义，$f$ 是单射。

结论：综上所述，$f$ 是从 $\langle \mathbb{R}, + \rangle$ 到 $\langle \mathbb{R}, \times \rangle$ 的单一同态。

方法总结： 证明同态与同构的方法：

1. 证明同态：验证 $f(x * y) = f(x) \circ f(y)$。
2. 证明单同态：在同态基础上证明 $f$ 是单射。
3. 证明满同态：在同态基础上证明 $f$ 是满射。
4. 证明同构：证明 $f$ 是双射同态。

---

难度: ⭐⭐
考点: #代数结构 #群同态 #单同态 #指数函数

💡 学习锦囊

📖 相关公式与知识点:

• 同态定义：$f(a * b) = f(a) \circ f(b)$。
• 单同态：既是同态又是单射。
• 指数运算法则：$a^{x+y} = a^x \cdot a^y$。

思路分析

同态的本质是“保持运算”。在本题中，$f$ 将原本的“加法运算”转化为了“乘法运算”。这种转化正是指数函数的核心特性。

🔄 举一反三

1. 证明映射 $f: \mathbb{R}^+ \to \mathbb{R}$，$f(x) = \ln x$ 是从 $\langle \mathbb{R}^+, \times \rangle$ 到 $\langle \mathbb{R}, + \rangle$ 的同态。
   查看练习答案与解析

   答案：见解析
   解析： $f(x \times y) = \ln(xy) = \ln x + \ln y = f(x) + f(y)$。 满足同态定义。

2. 证明映射 $f: \mathbb{Z} \to \mathbb{Z}$，$f(n) = 2n$ 是从 $\langle \mathbb{Z}, + \rangle$ 到 $\langle \mathbb{Z}, + \rangle$ 的同态。
   查看练习答案与解析

   答案：见解析
   解析： $f(n_1 + n_2) = 2(n_1 + n_2) = 2n_1 + 2n_2 = f(n_1) + f(n_2)$。 因此是同态。